package com.atguigu.substring;

public class ManacherAlgorithm {
    public static char[] manacherString(String s){
        StringBuilder sb=new StringBuilder();
        sb.append("#");
        for(int i=0;i<s.length();i++){
            sb.append(s.charAt(i));
            sb.append("#");
        }
        return sb.toString().toCharArray();
    }
    public static int maxLcpsLength(String s){
        if(s==null || s.length()==0){
            return 0;
        }
        char[] str=manacherString(s); //加工字符串，即1221-> #1#2#2#1#
        int[] pArr=new int[str.length]; //回文半径数组
        int C=-1; //中心
        int R=-1; //回文右边界的再往右一个位置，最右的有效区是R-1位置
        int max=Integer.MIN_VALUE;
        for(int i=0;i!=str.length;i++){
            //i至少的回文区域
            pArr[i]=R>i?Math.min(pArr[2*C-i],R-i):1;
            while((i+pArr[i]<str.length) && (i-pArr[i]>-1)){
                if(str[i+pArr[i]]==str[i-pArr[i]]){
                    pArr[i]++;
                }else{
                    break;
                }
                if(i+pArr[i]>R){
                    R=i+pArr[i];
                    C=i;
                }
                max=Math.max(max,pArr[i]);
            }
        }
        return max-1;
    }
}
